package cn.pugle.oj.leetcode;

import cn.pugle.oj.catalog.BitProblem;
import cn.pugle.oj.catalog.DynamicProblem;

import java.util.Arrays;

/**
 * https://leetcode.com/problems/counting-bits/
 *
 * @author tzp
 * @since 2020/9/24
 */
public class LC338 implements DynamicProblem, BitProblem {
    public int[] countBits(int num) {
        if (num == 0) return new int[]{0};
        if (num == 1) return new int[]{0, 1};
        int[] dp = new int[num + 1];//dp[i]表示i的二进制有几个1
        dp[0] = 0;
        dp[1] = 1;
        dp[2] = 1;
        int mi2 = 2;
        //递推公式, f(11) = f(3) + 1 (即f(8))
        for (int i = 3; i <= num; i++) {
            if (i > mi2 && i < mi2 * 2) {
                dp[i] = dp[i - mi2] + 1;
            } else {
                mi2 = mi2 * 2;
                dp[i] = 1;
            }
        }
        return dp;
    }

    public static void main(String[] args) {
        System.out.println(Arrays.toString(new LC338().countBits(0)));
        System.out.println(Arrays.toString(new LC338().countBits(1)));
        System.out.println(Arrays.toString(new LC338().countBits(15)));
    }
}
